public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class Solution {
    //解法1：迭代法
    public ListNode reverseList(ListNode head) {
        if (head == null) return null;
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }
    //解法1+：迭代法
    public ListNode reverseList2(ListNode head) {
        ListNode cur = head;
        ListNode prev = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }
    //解法3：递归
    //https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/solution/shi-pin-jiang-jie-die-dai-he-di-gui-hen-w2gm0/
    public ListNode reverseList3(ListNode head) {
        if (head== null || head.next == null) return head;
        ListNode node = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }
}